package developer.算法.动态规划.打家劫舍;

/**
 * @author zhangyongkang
 * @time 2025/4/8 15:42
 * @description 你是一个专业的小偷，计划偷窃沿街的房屋。
 * 每间房内都藏有一定的现金，
 * 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统
 * ，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * <p>
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：[1,2,3,1]
 * 输出：4
 * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 * 偷窃到的最高金额 = 1 + 3 = 4 。
 * 示例 2：
 * <p>
 * 输入：[2,7,9,3,1]
 * 输出：12
 * 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
 * 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 400
 */
public class Djjs {

    public static void main(String[] args) {
        Solution4 solution = new Solution4();
        System.out.println(solution.rob(new int[]{1, 2, 3, 1}));
        System.out.println(solution.rob(new int[]{2, 7, 9, 3, 1}));
    }

    static class Solution4 {
        public int rob(int[] nums) {
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0], nums[1]);
            //从第三家开始
            for (int i = 2; i < nums.length; i++) {
                //如果当前偷
                int current = dp[i - 2] + nums[i];
                //如果当前不偷
                int notRob = dp[i - 1];
                dp[i] = Math.max(current, notRob);
            }
            return dp[nums.length - 1];
        }

    }


    static class SolutionSelf3 {
        //每次偷不偷只与前两步又关系
        public int rob(int[] nums) {
            int[] dp = new int[nums.length + 1];
            int length = nums.length;
            if (length == 0) {
                return 0;
            }
            if (length == 1) {
                return nums[0];
            }

            if (length == 2) {
                return Math.max(nums[0], nums[1]);
            }
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0], nums[1]);

            for (int i = 2; i < length; i++) {
                int i1 = dp[i - 1];//上一步的结果
                int current = nums[i] + dp[i - 2];
                dp[i] = Math.max(current, i1);
            }
            return dp[length - 1];
        }
    }

    static class SolutionSelf {
        public int rob(int[] nums) {
            return f(nums, nums.length - 1);
        }

        private int f(int[] nums, int index) {
            if (index == 0) {
                return nums[0];
            }
            if (index == 1) {
                return Math.max(nums[0], nums[1]);
            }

            return Math.max(f(nums, index - 2) + nums[index], f(nums, index - 1));
        }
    }


    static class Solution {
        public int rob(int[] nums) {
            if (nums.length == 0) return 0;
            if (nums.length == 1) {
                return nums[0];
            }
            //每一步只与前两步有关
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0], nums[1]);

            for (int i = 2; i < nums.length; i++) {
                //来判定当前是否偷？ 如果偷的话 忽略掉上一步的结果
                int buToue = dp[i - 1];
                int tou = dp[i - 2] + nums[i];
                dp[i] = Math.max(buToue, tou);
            }
            return dp[nums.length - 1];
        }


    }

    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/house-robber/solutions/263856/da-jia-jie-she-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    class SolutionOfficial {
        public int rob(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int length = nums.length;
            if (length == 1) {
                return nums[0];
            }
            int[] dp = new int[length];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0], nums[1]);
            for (int i = 2; i < length; i++) {
                dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
            }
            return dp[length - 1];
        }
    }

}
